package dp.leetcode_213_medium;

import java.util.Arrays;

public class Rob2 {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int houseCount = nums.length;
        if (houseCount == 1) {
            return nums[0];
        }
        if (houseCount == 2) {
            return Math.max(nums[0], nums[1]);
        }

        //定义动态规划表
        int[] dp1 = new int[houseCount];
        int[] dp2 = new int[houseCount];

        /*
            由于房间是环形存在，所以导致"选择"会发生一些改变
                环形导致 第一间房 和 最后一间房是相邻的，所以这两间房不能同时被偷，于是可以分成两部分，
                dp1 来表示可以偷第一间房所获得的最大金额，那么dp1的取值范围 [0...houseCount - 2](闭区间)、[0....houseCount -1) (开区间)
                dp2 来表示可以偷最后一间房所获得的最大金额，那么dp2的取值范围[1...houseConut - 1] 、 [0...houseCount)

                两部分使用打家劫舍1的代码即可实现  两个部分去较大的即为结果。
         */
        //根据范围来设置初始值
        dp1[0] = nums[0];
        dp1[1] = Math.max(nums[0], nums[1]);

        //dp2偷不了第1间房，设置为0
        dp2[0] = 0;
        //只能从第2间房开始偷
        dp2[1] = nums[1];

        //为两个动态规划表 填表
        for (int i = 2; i < houseCount - 1; i++) {
            dp1[i] = Math.max(dp1[i - 1], nums[i] + dp1[i - 2]);
        }
        for (int i = 2; i < houseCount; i++) {
            dp2[i] = Math.max(dp2[i - 1], nums[i] + dp2[i - 2]);
        }
        return Math.max(dp1[houseCount - 1], dp2[houseCount - 2]);
    }

    //问题最终转换为对不同的区间进行 198的 打家劫舍1 操作而已。那么同样可以对空间复杂度进行优化
    public int rob2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int houseCount = nums.length;
        if (houseCount == 1) {
            return nums[0];
        }
        //dp1可偷第一家
        int[] dp1 = new int[houseCount];
        //dp2不可偷第一家
        int[] dp2 = new int[houseCount];

        dp1[0] = nums[0];
        dp1[1] = Math.max(nums[0], nums[1]);

        dp2[0] = 0;
        dp2[1] = nums[1];

        int pre1 = dp1[0];
        int pre2 = dp2[0];
        int cur1 = dp1[1];
        int cur2 = dp2[1];
        for (int i = 2; i < houseCount - 1; i++) {
            int temp = cur1;
            cur1 = Math.max(cur1, nums[i] + pre1);
            pre1 = temp;
        }
        for (int i = 2; i < houseCount; i++) {
            int temp = cur2;
            cur2 = Math.max(cur2, nums[i] + pre2);
            pre2 = temp;
        }
        return Math.max(cur1, cur2);
    }

    //优化重复代码
    public int rob3(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int houseCount = nums.length;
        if (houseCount == 1) {
            return nums[0];
        }
        return Math.max(helper(nums, 0, houseCount - 1), helper(nums, 1, houseCount));
    }

    public int helper(int[] nums, int start, int end) {
        int pre = 0;
        int cur = 0;
        for (int i = start; i < end; i++) {
            int temp = cur;
            cur = Math.max(cur, nums[i] + pre);
            pre = temp;
        }
        return cur;
    }

    /**
     * 另一种写法，利用Arrays的copyOfRange方法。
     * Arrays.copyOfRange(T[ ] original,int from,int to)
     * 将一个原始数组，从下标from开始，到to(不包括to) 结束，复制到一个新的数组中。
     */
    public int rob4(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int houseCount = nums.length;
        if (houseCount == 1) {
            return nums[0];
        }
        //不选最后一间房
        int[] dp1 = Arrays.copyOfRange(nums, 0, houseCount - 1);
        //不选第一间房
        int[] dp2 = Arrays.copyOfRange(nums, 1, nums.length);
        return Math.max(robMax(dp1),robMax(dp2));
    }
    public int robMax(int[] nums){
        //新的数组还要进行边界判断，比如{0,0} 分割后就是{0}, {0}
        if(nums.length == 1){
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for(int i = 2; i < nums.length; i++){
            dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]);
        }
        return dp[nums.length - 1];
    }
    /*
        优化空间
     */
    public int robMax2(int[] nums){
        int noSelect = 0;
        int select = 0;
        for(int i = 0; i < nums.length; i++){
            int temp = noSelect;
            noSelect = Math.max(noSelect, + nums[i] + select);
            select = temp;
        }
        return noSelect;
    }
}
